<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>

    // 封装哈希表类
    function HashTable () {
        // 属性
        this.storage = []
        // 记录表中存放的数据的个数
        this.count = 0
        // 哈希表当前总长度
        this.limit = 7


        // 方法
        // 哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            // 1.定义hashCode变量
            var hashCode = 0

            // 2.霍纳算法，来计算hashCodede值
            for (var i = 0; i < str.length; i++) {
                // 获取当前字符的unicode编码
                // str.charCodeAt(i)
                // (anx + an-1)x
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }

            // 3.取余操作
            var index = hashCode % size

            return index
        }

        // 插入与修改操作
        HashTable.prototype.put = function (key, value) {
            // 1.根据key获取对应的index
            var index = this.hashFunc(key, this.limit)

            // 2.根据index取出对应的bucket（桶）
            var bucket = this.storage[index]

            // 3.判断该bucket是否为null
            if (bucket == null) {
                bucket = []
                this.storage[index] = bucket
            }

            // 4.判断是否是修改数据
            for (var i = 0; i < bucket.length; i++) {
                var tuple = bucket[i]
                if (tuple[0] == key) {
                    tuple[1] = value
                    return true
                }
            }

            // 5.进行添加操作
            bucket.push([key, value])
            this.count += 1

            // 6.判断是否需要扩容操作
            if (this.count > this.limit * 0.75) {
                var newSize = this.limit * 2
                var newPrime = this.getPrime(newSize)
                this.resize(newPrime)
            }

        }

        // 5.获取操作
        HashTable.prototype.get = function (key) {
            var index = this.hashFunc(key, this.limit)

            var bucket = this.storage[index]

            if (bucket == null) {
                return null
            }

            for (var i = 0; i < bucket.length; i++) {
                var tuple = bucket[i]
                if (tuple[0] == key) {
                    return tuple[1]
                }
            }

            return null
        }

        // 删除操作
        HashTable.prototype.remove = function (key) {
            var index = this.hashFunc(key, this.limit)

            var bucket = this.storage[index]

            if (bucket == null) {
                return null
            }

            for (var i = 0; i < bucket.length; i++) {
                var taple = bucket[i]
                if (taple[0] == key) {
                    bucket.splice(i, 1)
                    this.count--
                    return taple[1]

                    // 缩小容量
                    if (this.limit > 7 && this.count < this.limit * 0.25) {
                        var newSize = Math.floor(this.limit / 2)
                        var newPrime = this.getPrime(newSize)
                        this.resize(newPrime)
                    }
                }
            }
            return null
        }

        // 其他方法
        // 判断哈希表是否为空
        HashTable.prototype.isEmpty = function () {
            return this.count == 0
        }

        // 获取哈希表中的元素个数
        HashTable.prototype.size = function () {
            return this.count
        }

        // 方法扩容
        HashTable.prototype.resize = function (newLimit) {
            // 1.保存旧的数组的数据
            var oldStorage = this.storage

            // 2.重置所有属性
            this.storage = []
            this.count = 0
            this.limit = newLimit

            // 3.遍历oldStorage中的所有桶
            for (var i = 0; i < oldStorage.length; i++) {
                // 3.1.取出对应的桶
                var bucket = oldStorage[i]

                if (bucket == null) {
                    continue
                }

                for (var j = 0; j < bucket.length; j++) {
                    var tuple = bucket[j]
                    this.put(tuple[0], tuple[1])
                }
            }
        }

        // 判断质数：判断传入的数字是否为质数
        HashTable.prototype.isPrime = function (num) {
            // 1.获取num的平方根
            var tamp = parseInt(Math.sqrt(num))
            // 2.循环判断
            for (var i =2; i <= tamp; i++) {
                if (num % i == 0) {
                    return false
                }
            }
            return true
        }

        // 获取质数的方法
        HashTable.prototype.getPrime = function (num) {
            while (!this.isPrime(num)) {
                num++
            }
            return num
        }

    }


    // 测试哈希表
    // 1.创建哈希表
    var hast = new HashTable()

    // 2.插入数据
    hast.put('abc', '123')
    hast.put('cba', '321')
    hast.put('nba', '521')
    hast.put('mba', '520')

    // 3.获取数据
    alert(hast.get('abc'))

    // 4.修改方法
    hast.put('abc','111')
    alert(hast.get('abc'))

    // 5.删除方法
    hast.remove('abc')
    alert(hast.get('abc'))
</script>
</body>
</html>
